/*
 * @lc app=leetcode.cn id=46 lang=golang
 *
 * [46] 全排列
 */

// @lc code=start
func permute(nums []int) [][]int {
	res := [][]int{}
	permuteHelper(&res, nums, []int{}, make(map[int]bool))
	return res
}

func permuteHelper(res *[][]int, nums []int, list []int, m map[int]bool) {
	if len(list) == len(nums) {
		tmp := make([]int, len(nums))
		copy(tmp, list)
		*res = append(*res, tmp)
	} else {
		for i, _ := range nums {
			if _, ok := m[i]; !ok {
				list = append(list, nums[i])
				m[i] = true
				permuteHelper(res, nums, list, m)
				delete(m, i)
				list = list[:len(list)-1]
			}
		}
	}
}

// @lc code=end

